package com.sunny.l35;

import java.util.concurrent.LinkedBlockingQueue;

public class Solution {
    public void connect(TreeLinkNode root) {
        if(null == root)
            return;
        int size = 1;
        int ind = 0;
        TreeLinkNode prev = null;
        LinkedBlockingQueue<TreeLinkNode> queue = new LinkedBlockingQueue<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeLinkNode tmp = queue.poll();
            if(null != prev){
                prev.next = tmp;
            }
            ind++;
            prev = tmp;
            if(null != tmp.left && null != tmp.right){
                queue.offer(tmp.left);
                queue.offer(tmp.right);
            }
            if(ind == size){
                ind = 0;
                size <<= 1;
                prev = null;
                tmp.next = null;
            }
        }
    }
}

class TreeLinkNode {
    int val;
    TreeLinkNode left, right, next;
    TreeLinkNode(int x) { val = x; }
}
